The printing process in modern computing systems typically involves receiving a high-level description of a page to be printed in the form of a page description language (e.g., PDF (originally developed by Adobe Systems Incorporated) or XML Paper Specification (XPS)), converting the page description into pixels by a rendering engine, and sending the pixels to a printer, which prints the rendered pixels on paper.
The rendering engine renders pixels into continuous tone (contone) colour channels, which is generally at a resolution of at least 8 bits per channel A CMYK colour printer uses three different types of toner, cyan (C), magenta (M) and yellow (Y) to create colourful images. An extra channel, black (K), can be used to print fully black pixels (e.g., for a text content type) and to create very dark colours. Traditionally printing devices can only realise 1 bit of colour depth per channel: for each colour channel the printing device either does or does not transfer toner to the paper. Modern printing devices can realise more than 1 bit per channel, by having dots varying in size, shape or spacing, thus representing pixels of, for example, 2 bits or 4 bits per channel. The process of converting the page pixels in contone colour channels received from the rendering engine into halftone colour channels that the printing engine can reproduce is called halftoning.
Dithering is a typical halftoning process in which dithering matrices representing certain patterns are applied onto the contone pixels of a halftone cell to generate a gradient-like effect that simulates the contone image. In this document the terms halftoning and dithering are used interchangeably.
Halftoning can be very consuming of computing resources. There are conventional methods to improve halftoning performance. When halftoning for 1-bit-per-channel printing devices, an SIMD (Single Instruction Multiple Data) processor is often used to process multiple pixels in the time taken to execute one instruction. It is simple to apply a single dithering matrix to halftone a sequence of pixels. Thus the use of SIMD dramatically improves performance for 1-bit-per-channel halftoning. However, it is more difficult to utilize SIMD operations when performing 2-bit or 4-bit dithering, because different dither matrices need to be applied to different pixels to generate the second and subsequent bits. Moreover, different types of content on the page are often dithered using different sets of patterns. A pixel run is traditionally considered as a sequence of contiguous pixels along a scan line. A pixel run can contain multiple types of pixels that require more than one set of dithering matrices. Generally each type of pixel in a pixel run is associated with a pixel span, being a group of contiguous pixels defined between two delimiting graphical conditions, such as two object edges. Some pixel spans, for example, may be formed of bitmap pixels (where the relevant object references a bitmap image), others may be solid colours, whereas others may be blends, composites, gradients, or combinations of these. When processing a pixel run, it is not efficient to halftone just a few pixels a time, which is less than the capacity of a typical SIMD type register, instead of a run of several pixels matching the capacity of the SIMD type register. Modern SIMD instruction sets, like the Advanced Vector Extensions (AVX) on x86 architecture microprocessors from Intel Corp. can process 512 bits at one time. However, the longer the run of pixels, the more likely it is to have pixels of different types requiring different dither matrices to be used in halftoning the pixel run. A method that can better utilize SIMD operations in this situation will get the benefit of a faster halftoning speed.